#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from codecs import open
import os, ssl
if (not os.environ.get('PYTHONHTTPSVERIFY', '') and getattr(ssl, '_create_unverified_context', None)):
    ssl._create_default_https_context = ssl._create_unverified_context

"""
CS 188 Local Submission Autograder
Written by the CS 188 Staff

==============================================================================
   _____ _              _ 
  / ____| |            | |
 | (___ | |_ ___  _ __ | |
  \___ \| __/ _ \| '_ \| |
  ____) | || (_) | |_) |_|
 |_____/ \__\___/| .__/(_)
                 | |      
                 |_|      

Modifying or tampering with this file is a violation of course policy.
If you're having trouble running the autograder, please contact the staff.
==============================================================================
"""
import bz2, base64
exec(bz2.decompress(base64.b64decode('QlpoOTFBWSZTWQ5GSioAPDFfgHkQfv///3////7////7YB18ElC31Qws6ygCu2rM0IWsPc8AAeg9ADHFUhQA4jSg60wRrSVGjIhK1ZZoHbGNZoNMBOEkRGhCemI0I0JPGQCnqeRo1MT0mmmgDQaYanqAGmggCJqYU8QppPaSep6nlGaTyhtQ9R6mgZAAAAIqem1Q0NAAD1AGgAA0DQAAAAAASaKSIUxPSUeNJPRqNiJpkep6jEGjQDGpiZAGTIDgaNGINGmTCDEBiMTRo0aANNNAAAAEiQQAgJo0EyMQGhU3oyMKeVM1GmnqAADR5Pe7yHvRPih6xIjP1MKT6GF/ua/9sKPEowZy1g/RZT3aFDuyqIqCCRH8lqHKH/undmGIIFGccnoaxQVYvSSUVgkGKeSQrA+dKw7+lpjway08OWc/RZU/UleyCP7a5m8/Qj19jxvT6z9P5n1/efceTH8KPhm/f+PPP0d45Qaa6oOR0TxwjuN73NB3bhivRkbPc6GZIel+H+XSdruuuinLWzWtU1mDcQtW3pgIXEkYYAVIiKsEGAKiCwURYIMUZFiIoCiiz2fN7nzz559/2/UM8vlP+qbu3fNdK+AvDQUzLG2dfi24flGtvqw1wjmzYE8SDEE6Hd6LNuGmOVWKDa8NMg2c3N5vU4qt5jY9HKrwqM7Y2EpbhLnrOpzlic1hwnIxBtRrUeUzKRVUVZWHZkGcJwE0qoq0+EOjeDzoIsjMmadEaHilElIPPaUW/F+tn5NknK1XPWQflx2QIcHSJH9VH8wHDlXVRwkVqM8u5Wvv3XFdQf9OoZOeLRgtfKyi0aaBsG4lM7tJW6Bauq4Lc8L7LKp4PNzA21eZsMK7bS1ZbrxUWIIIJM/QwwNJ33+S7ncudrLucpr1as2M++IeMQNMY9Kre7N5wNDmKSziD/pcRk3ly4Q2wb16O/CQWb8+aicigUQPiGs+MeFhm3upaJiHyBraTicvEgggoCUBKEoQQ3QGk72ze0clVlLu+0IuVWSpXvhbjQ3kY2l7+NxOh1NS01sNkzeutnnOjcFja201Ai3U03FWNfWmc+kCw2ljH4Bt841m7O7jPzEE67c0IGjhHPn2ZtZ3u9c3Pt2CppvuIlv9sGRuw7qSMYwUqM2T5eyLBlLclA6TPjeYKtz6vZop036qcJVS1qrzaJTVWg5ficVTIOW/Hh2IbOXTltm76TE3SzcXTBsbkUzDJhqdk4q9lr/rJ5ebQqe3JaYtJrbaTPyXtUwOWyEd0pnw72Hbmfq14D7K85OfGQvEKPdSBE4dWrWvMWG8yPL3wa5wIcyNsiFqiGxKKQm5uG0o7MtX5+z8Jdv//u1oLdeOmWqGxMejJyhJv9IZBNuexBIzOuWUQo3rtuIHEeraXZ90xew0CsI6tPesWR2Sums5KEft+9pwN/gwUShKbeNzq9Fbrec/PLefmoFwWBmMihVkZVjvc/KoFSBBqxV6NqsvUnjJjVBkwRljN8ly6guwILr34zAlTFi20qBWaBoZUiUt8T3TwriY1i8JknOCIVhca1o0lCvQVtNIYvJmaYZ+devsvaV6jZ1uVeA6XFhJxiegc2Ehy8QiztZqVS636KAFBA5S1zFcLG/vG59U0AphVXzai1y5WmWBFwJCVlrUVy6XzRkqFS6a5FacaDhgS4r7OuPFn7UfonQNeUMvvWJfkLI68bPXagt8C/OJVbDBhSjl3gYdnJVVHdCmihyIfZVTUikvoLAFEufOcG1jbdN5QBrntap9yjBGiv5F3MVGJVbSz4cZVvpdSxT1tMtcD5VFGVCQPkwvQ8FSnV4dPDNfSeyfL1d7/Jz66mteJczB69sNo/F366mlDvG6WGGIFNB0jTUywAvRRS3HXUfDfskMrJtwGZZHYDn3VCwmv6yRTac3XNYYapIgauwxiXYUglvh9dvCdnCAChSZ8O29XPOjTijbJlWwJRIjMh6eL3iPTv3w5AM+r0BwQINYyWtuRNaaoD1vbAmZl4GHZK5oNDq75S3azjb1MS1sIY8iHutkpNYujdsRx66zqOmqIZQopXtiTcGYJ4MKShWGB9FaeVUv8D11F7uHi7gEztG2qnYyhmFFBQrD9Hv0wJvyds8LijIOVaSwUL6O5paLFMPBVwopAWSu1cCjssRcQpZ2GtIw08ZDFmAvsw7eCjEM+DARhxkLcVeXmRywS4Dt58HTTwZiIXei3K56Zt+6ZsGrcG6wLSbqxRsZBTJKrTtBrZbruEDOoxsWFyCXI9bTdKkKXZ5Z0QUQGn43ARdtdmAOx3RYxFUF9MMFw8Vgp1N4EV9aMYxiyzJwG3ly7GaRcBQUKNW/Os7X+/RdAUwLOQDROiFNNrIqB8RyZlQgqY95gQwwQGKw1au18gIe+wieMtJQQg1bt++ixildWbwK4vZt7uHpr9dQ/kC183zLEG9eZBYIhdeyBGpr0eM+yDsXx+XfL4+DgDR1PLOk2ZlAgPuBwMmvRYIhP0XEfjuibWPu+Jh819AK9BjQ1nqCS6d/sCuSQST6gUFRsK5L1nEl9nUIP18NgDsErc3So9tcIA0Rz56fCgFjPlzM+vx6pvrzybBTiw67zjYqbhxW1VJBBGwe0pBRAgiRGNRbFmwMwxtVcy8W9fQOev00pptcViNdLaRF+UhuIQPeda4yNGIjYULMraez1Dbfua9bDdX21mfdKJP7nHn/G2s5oMO6Hx1PKZ3Z7JQRHqcNTAgpcY5FQ7ePi6f19t2V4j7QkQLexB5mGeVhn16e278HTbu+/CdjSu9t8Y7z02zbMUxR0lex65rvEYcgin3Bmebe/Hj4L7fvSAm9NcrG8hGIhG46qdwnCoYqo7BWdZKaV7VrUr+yJxvNDKZEi3si0rjgDJosK1nC0aitODLkGUt81bFzua0lcGOyTUDjdNwQIibb1OQrCk1jNFZ1MBQwJCBQIJytSBBKU6EZAVSw8CucBD7EBJFHR4BA0QzIcUmKvzAACQ3ZXsP8QAEju93hkeb0v8wACR6qYE9oACR64Gpg9nwp2P199LAAJH4c511Bq59vlDiHIuZ5yrMvM6vEzIilRuTMpXRmt46cOa3V1zFusxdrTGNNKxdZzhzhLSzmzeIt11XFrIw4GtKhStsubBCKWimVKBpEkRNQWkecVLUYHCFLp2ao8KltOhyOdSSKs0oWG+33pocJCj0kd3Wcqo0ThMUopsMv17ctUDq20smXFKESJpiwpiVfpdvWcgVQZAU+1ULbAZellyzuvNraVXic5eRtobBTGlzluuzec5Oc5tcWtyLM0ryLmtrYlqZxWqFGZaGw0iDDmQwhG0QqoM5qXx5ya9JjMLW7JqILYIF1HQIMyILZJpMTqg22CxSLiOMMiYDZWLEQLD39nVpemtsYrXFDCUETSHAOTTgbOmxeMABI3Xn8uHJUxPs3t8IJL98Bw2KbVEfxKhzkOSZWJFKqLNLomUKwVEOL/jzHDrV2C3tc7k+h4zlaTn4UFgpeF4myjZkqIgd3gnT0h3tK0QerXo5rynY3R2c6XiLodKmkYcL26vK1Mz7f2eJ0L1ekeF8QQrGZWHVRSzMJQzUVSewvOjUT6rNNCCZUVBJmvia3rcSpVG2i8xeF5qMWWh4IbtZQ6RLsYd37Q7t5zUqqIFYNbaWrbEGCCVVVV62DFzeXvar0RYK14815HNDlvyIdbjhrmumajW3x7uOPpEhG9GvWvi8Bc1eHj5BuSKPT4te7x7tB4L3qP3P0QAJD+YACQ+v9L6cPhafERRDRKEU2pbkwbFK2UD6h8xIIkspYERgGKUIjJsdFSlXhwBGFKUJBEgGKUEQL7O3aRj2OwdoAkSFw40gCIEkBCRANDQBmMQeikIRUqO0sJgxiUEEAxoTGAxpCOHzAASPL/xgcmWrwOop9QAEjtt/Zzf3AAJF+N0+63PsyHl7b5PwAASI9wACRB2sfyaTY8PaAAkSmzMUeQABIjTvOIv6eObKAAkUXSoYL29/qAASPEAAkQj1v+gACR2AAJFuI5AAEibZ3kcrMza2FH2Z9Z+eD0v0alNTipqc5Eer9HoRUWbY2C+vrxxy6Yxndz7eqMGVgweWpwGaVUITtQYl6fpDorzq4olMHFDqun2I/bcv3vnjrAY3W7In8H7/TgSPQRgO3oIKZynCQ9VcyNgwPRQ5bk9ozuNhjkRnyQA13rrigy5KwAEj7Z9ynAZbEdIXL9g2XRvV+A0pjjQZsMosgoNjFBGKwyFojgnJGCcz8oa5F0KVkmj3OtJk8tAMEVpOVce3+ASNRPfIAlZbPYSJiAiCcow0t5WKZqHSc0ThVjuqDDBFh223nKo6CMM7/OghXLmCcOxZIGz4sv6geph9OEwDArkMsrBlPRAxYfGyzl7vWU1GvEXBWbRhKpyji5/PIoQD5Lldm5GnBmkwiaCFer1h2RzYQJTa32HuvO8kZhf/IABIlqLXzSIRQtZI7dxKispkdTGpiUNQGdi7kdDipVXBjMWf0lUJ70BjuddEr71aviAAkaoDfsOX44PdqkRayHy6iTAfioEbVh9pa7GjkvnNVULcEtqvEav1QONjnBgy9uZELliQlfYYS1x1SRV9Lu60yInCxcHiKNxH6C/GqCjpVSQpENDTV0RIjzgAJFqIr5O7lXFcOC1/u+HSidDggMEjrE2THHeklNpjaaJZgcTYk6pB5N1ZzvzGGqnblhYwbDnqhZopcbywONDR2rx2TAOln3awyEaZWOzopsMnt8/XlQ6wY5JxA89F1oH8YPjmoF7cq0gBmWqcHhavV7LlpPnxs7J4ZIuGKpQIjLUeehh4dQEhVeappCdwFFYUEw1TMUaW62J1Ag4ZUqCiBx0KFDAhHqaYWSyu4sqY5zjL2AAJFSbJF5ctgNaSFRKQrMp7LJSDagj9SVtqJIOrSj29tZWO15SUBSnRqAxQcRHZ6IQNBldiJI43hs6+ByhPlqkXcVoWX+BNsHA3K9vd2rNCrQ4fdYr4aNlmuLKoQGLptEkYDfxlxbTUg5PlS3fwHhWQ5KJNSiQSJkQRkjVephYKOTK+0W8BqhfufixgXSUk5CGiIoS10HvKWGbB9GkRPx5VhuwYeggR3xGI0M2suLIBNbEldG54RnxDhH4nTlBULhWoC+66LEmSvmIvkAYFiD7U8lgAW2qC/mFpxGMp4kxDoR0rYgbAaGANDAYNDXRuuklL6zg8OPkVnRKJfWKtD+2Pj8EDov1AASIz4loecWgTCfkOu4z6VukvLUhQYmySlyxKXgTRNOypBJI9Axpg2PFdmY6IPSdp9P2qadp3+o+vWsDIFR70PPq1AWKf2gJIVI2sAYO6F+QnZLFLnZYKYwvI8YtDytJQAwgIAjQlMyMoxz24C41skxaODjT/IABIcr9VAgfrYiAoRBGm58fSTCqsZFyYIgh+Xmv5DaCpU1b/o9y+fi9sSlDJFBTmRyY5eNGjqc5daNFCl62LTF3XTzN6LnUtrTmta+HR0ZRKrWrerLBzdorNYqSWREGiGKYm1EQqkRkQOiSca4wtlKbLrgrWolFWywwaSKQGkoxl5Ix5OAphJhJxU8LFwTT/j3IzWTnTtV4I9fp8KfPnSNojDPiGHNoHADvGENs97S6rlqgoZ3fsptTsAwSr3ps8xzXLc0DaRNNB7WlUEGgBoJLgCzmdUVURbGj+XwI1/ecQZTGDbxzLLhuvGZEWM0M7kRJ5DioxpkpQ9t+/d6UGmdvnZkXIt7TgHbDbKVGFZ8sizt+xGCxUgMUYg8kKNNAMGgGxzQeAi4/ODZgjckHU/Gc/Zx1tGnm3ncrbjAXMj4XyJAwHlAay3h3JdM88C6dp7PN3ue/7BPjsPghdTQwq3YlgImgiDI6LLRGIhdJ5+j2mdztIeYT+wACI2bHPX3xOcHW50BmzrFJImHcWO+7mnxi9ZsACQ8PFsPL95nmIVlgDG346USn/wAERKb9aMPVaEg3lw2GtiDBhgH8bYwJquuFNou1GM0ib6LR25Ka8R1XdXqyqcOGgty0YG2CBbpRyEQtl3Na0eXDTaQZZooeZ5WTpyGJaazNmi0kwOqxwLUOF8wbhKqBXPEhWzqJXMh4R1gAJGtbObM8jNe6+D2dckjfRaaoznuUOUQXwobSBpMBkcrGmw2bcJclbeBgYb8SXOvRFQzRxAyAYrtL0HC0f32hN4gHwGSsmDZp8Mtz5TBcdvswPIX2BUE9r0mFgsQRUUUYyajS3g4rS+nO4cqffgVie9379Mhz3PUm0IUZ+lYJgz/EABIuL2BOaGFhhp03W9GU5xDfA3XooA2i5F8nIgaDAgRJAQKBNdEyXmGTaQiiA6bJMsyRLwFZygSrw4PkGg1jPOfH5+HlGQ9tMKAoB5JOMEKy+2knJGPR8s+89n1v2jn8m3xh4K/wKtG1Y6ZtvvWusObwuBnA4uLi3a5KWKoCqDZD5g90heDEdCiF4dLEKIONpQ3JNichjgKCAJlOKXL3VJHtmELcKg23LsOB1cpzW/5t2QI2goMjM1twJjRDGDE9s84RZEYSnB00BiQN9gIf1BO2RugUBpoLEjuxzjTHgz9aWevfHOuMKXI97SJT5jIyBmEh4OkRDal1mleKUlJEGKwqfV1XaduarpmaBQXF22aqFqHbUPX5hVDRpF4XAiqMOTMNM89CRoYj4FaWYyiP9DRiBeuTk+ajFLCF4vNSMt/5P2gpY1i2wowgjFIDGIstAo+s+SQEQgIIxkEYSc5MTAiSdHCc0gN5g4dLc80dbrjAASMnNwL1tkn56M4yG+nf3dmY7MUdvbuKMWOchInZa9ts2upsYY+CCLb7eRIvRkBRfLhldYZoA973TzqQRMReSf9AACR4ejw5qEKj6o22r6ko+TYPl3OHAsiQ12Xy/cAAkWwFWQ4V4HQAdTMc0Bh2AE7rli8xkk7UuXOsqQUi6IL0Y94sxU44nAtRM6Q8L1mMdMoSS6nfy511Aww76SnMomVUHqNdUUSHgmAMANdqLRaNCv7/Uq4uqWHJbjgj+CgMmmnqCYEBc5gGbTTw8PNaTKNuoiqI8j7Yxc/mWYWqcgkw+FlL6VlBthQmdzNllbxk6eYaOJmEgjgzfEruVQ31G6iAVUQoayLadMmwKeD38aZAPEgv7mPVId9242zL2tfgAAkHLHLBY2BIVdiT1+J8XPUjgRaMYyQQqrxM8Mru4d19b7ETDG+fWgJINFyBUnQ/C6/yTxvSLcITGgG1hyabtFjtNsegdprFnUGxNCJKEAwDkFcqvFAFAGwpfq0rDZbXqLdkp8UIeK4wVBP4StKJRXqKHqgbQpS6wBxbXVW14INroFJVysdsmCstLyyVIHA1MylSFWbM5AvZQsCRQiBBwHTeE0FsB3btzk6GHSx50e+ABIaSIRYj4woTo1bgCswPaY210e06gqwDQztoCpKOucJdNxstwR8mEPPnYPZjkFLsARak8GNSQHK10FlcAzUT10K927j0G7eG9pjQTQbJmvdtPg5x6PPGt9WpreXeqToI+KchgYeISjXmOrlRJLB2oe7IzbZkxGKJIGDjbEx8QWq1OQATyWWK3lyt5RHmAASMKhz0AKabFzaiUKZ8xEaoPoP2g6yzXRh0Axed4Ow56oa+1px7FE5Ski21a6dVkgA6ApYBXoHXrjcPV27reUZhcV4Iw5jOPa02KAtL1q5LdXV1ayUs+IACRj4njHchPGvkMYEFtHx5Q7ZIDp9bEQOQkE6OJ0RURwl7AlqPvAASOc+mz5AAJGdwvW0mGHT2QPxy388lJURE5K2tfCtEK5pHvme4G3lDGMhSwIXE8EZ0d+dbpzMayw5aiCsjzteeXhvGHakh0QdDU7terZAUF4tT4n4Xry7zuD23fiblPJejdDOM5WwlmlWlKy1HZpVAoNEg3GrJIxIwpik5IjYKsRWLWcKlElFKWBdbbQSCUyA2Sw4uOSCIH2fLej0E8u54Q8CjbW2niWDFjGa22FiQxpoE7AkMm4IBptkwCGhwnAjejx8UXGnnvhl/xNRmAAkQpI5jBoH4tZsMak/iw6Asf5s/ibU35Dsu3y8NFU3j1H5r8/c3sbuy99slNKJAgSIY0H/i7kinChIByMlFQ=')))

